// 爬楼梯
// 给定一个共有n阶的楼梯, 你每步可以上1阶或者两阶 请问有多少种方案可以爬到楼梯

function climbingStairsBacktrack(n) {
    const choices = [1, 2]
    const state = 0
    const res = new Map()
    res.set(0, 0)
    backtrack(choices, state, n, res)
    return res.get(0)

    /**
     *
     * @param choices
     * @param state
     * @param n
     * @param res
     */
    function backtrack(choices, state, n, res) {
        //记录结果
        if (state === n) {
            res.set(0, res.get(0) + 1)
        }
        // 遍历所有的选择
        for (const choice of choices) {
            // 剪枝
            if (state + choice > n) {
                break
            }
            // 尝试做出选择
            backtrack(choices, state + choice, n, res)
        }
    }
}

console.log("climbingStairsBacktrack: ", climbingStairsBacktrack(3))

// 暴力搜索 dp[i] = dp[i-1] + dp[i-2]
function climbingStairsDFS(n) {
    return dfs(n)

    function dfs(n) {
        if (n == 1 || n == 2) return n
        const count = dfs(n - 1) + dfs(n - 2)
        return count
    }
}

console.log("climbingStairsDFS: ", climbingStairsDFS(8))
// console.log("climbingStairsDFS: ", climbingStairsDFS(100))

// 记忆化搜索
function climbingStairsMEM(n) {
    const mem = new Array(n + 1).fill(-1)
    return dfs(n, mem)

    function dfs(n, mem) {
        if (n == 1 || n == 2) return n
        if (mem[n] != -1) return mem[n]
        const count = dfs(n - 1, mem) + dfs(n - 2, mem)
        mem[n] = count
        return count
    }
}

console.log("climbingStairsMEM: ", climbingStairsMEM(8))

function climbingStairsDP(n) {
    if (n === 1 || n === 2) return n
    // 初始化dp表
    // const dp = new Array(n + 1).fill(-1)
    // dp[1] = 1
    // dp[2] = 2
    // // 状态转移
    // for (let i = 3; i <= n; i++) {
    //     dp[i] = dp[i - 1] + dp[i - 2]
    // }
    // return dp[n]

    // methods 在动态规划中, 当前状态往往仅与前面有限个状态有关 这时我们可以只保留必要的状态, 通过"降维"来节省内存空间
    // 这种空间优化技巧被称为滚动遍历或滚动数组
    let a = 1, b = 2
    for (let i = 3; i <= n; i++) {
        const tmp = b
        b = a + b
        a = tmp
    }
    return b
}

console.log("climbingStairsDP: ", climbingStairsDP(8))

// 给定一个楼梯 你每步可以上1阶或者2阶, 每一阶梯上都贴有一个非负整数, 表示你在该台阶所需要付出的代价, 表示你在该台阶所需要付出的代价
// 给定一个非负整数数组cost 其中 cost[i] 表示在第i个台阶需要付出的代价, cost[0] 为地面起始点 请计算最少需要付出多少代价才能到达顶部

// dp[i] = min(dp[i-1] + dp[i-2] ) + cost[i]

function climbingStairsDPCOST(cost) {
    const n = cost.length - 1
    if (n === 1 || n === 2) return cost[n]
    // 存储子问题的解
    const dp = new Array(n + 1)
    // 初始状态
    dp[1] = cost[1]
    dp[2] = cost[2]
    // 状态转移
    for (let i = 3; i <= n; i++) {
        dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i]
    }
    return dp[n]
}

console.log("climbingStairsDPCOST: " + climbingStairsDPCOST([1, 2, 3, 4, 5, 6, 7, 8]))

// 无后效性: 给定一个确定的状态, 她的未来发展至于当前状态有关, 而与当前状态所经历的所有状态无关
// 带约束爬楼梯
// 给定一个共有n阶的楼梯, 你每步可以上1阶或者2阶, 但不能连续两轮跳1阶, 请问有多少种方案可以爬到楼顶
// 状态[i, j] 表示处在第i阶, 并且上一轮跳了j阶
// dp[i, 1] = dp[i-1, 2]
// dp[i, 2] = dp[i-2, 1] + dp[i-2, 2]
function climbingStairsConstraintDP(n) {
    if (n === 1 || n === 2) return 1
    // 初始化状态表
    const dp = Array.from(new Array(n + 1), () => new Array(3))
    // 定义初始状态
    dp[1][1] = 1
    dp[1][2] = 0
    dp[2][1] = 0
    dp[2][2] = 1
    // 状态转移
    for (let i = 3; i <= n; i++) {
        dp[i][1] = dp[i - 1][2]
        dp[i][2] = dp[i - 2][1] + dp[i - 2][2]
    }
    return dp[n][1] + dp[n][2]
}

console.log("climbingStairsConstraintDP: " + climbingStairsConstraintDP(3))

// 给定一个nxm的二维网格 grid，网格中的每个单元格包含一个非负整数，表示该单元格的代价。机器人以左上角单元格为起始点，
// 每次只能向下或者向右移动一步，直至到达右下角单元格。请返回从左上角到右下角的最小路径和。
// dp[i,j] = min(dp[i, j-1], dp[i-1, j]) + grid[i][j]

// 暴力搜索
function minPathSumDFS(grid, i, j) {
    // 容为子元素单元格, 则终止搜索
    if (i == 0 && j == 0) return grid[0][0]
    if (i < 0 || j < 0) return Infinity
    const up = minPathSumDFS(grid, i - 1, j)
    const left = minPathSumDFS(grid, i, j - 1)
    return Math.min(left, up) + grid[i][j]
}

const grid = [
    [1, 2, 5, 4],
    [3, 2, 3, 3],
    [1, 4, 2, 5],
    [5, 2, 1, 2]
]
const n = grid.length - 1
const m = grid[0].length - 1
console.log("minPathSumDFS: " + minPathSumDFS(grid, n, m))

// 记忆化搜素
function minPathSumDFSMem(grid, mem, i, j) {
    if (i == 0 && j == 0) return grid[0][0]
    if (i < 0 || j < 0) return Infinity
    if (mem[i][j] != -1) {
        return mem[i][j]
    }
    const up = minPathSumDFSMem(grid, mem, i - 1, j)
    const left = minPathSumDFSMem(grid, mem, i, j - 1)
    mem[i][j] = Math.min(left, up) + grid[i][j]
    return mem[i][j]
}

const mem = Array.from({length: n + 1}, () => Array(m + 1).fill(-1))
console.log("minPathSumDFSMem: " + minPathSumDFSMem(grid, mem, n, m))

// 基于迭代实现动态规划法
function minPathSumDP(grid) {
    const n = grid.length
    const m = grid[0].length
    // 初始化dp表
    const dp = Array.from({length: n}, () => Array.from({length: n}, () => 0))
    dp[0][0] = grid[0][0]
    // 状态转移, 首行
    for (let j = 1; j < m; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j]
    }
    // 首列
    for (let k = 1; k < n; k++) {
        dp[k][0] = dp[k - 1][0] + grid[k][0]
    }
    // 其余行列
    for (let i = 1; i < n; i++) {
        for (let j = 1; j < m; j++) {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        }
    }
    return dp[n - 1][m - 1]
}

console.log("minPathSumDP: " + minPathSumDP(grid))

function minPathSumComp(grid) {
    const n = grid.length
    const m = grid[0].length
    const dp = new Array(m)
    dp[0] = grid[0][0]
    for (let j = 1; j < m; j++) {
        dp[j] = dp[j - 1] + grid[0][j]
    }
    for (let i = 1; i < n; i++) {
        dp[0] = dp[0] + grid[i][0]
        for (let j = 1; j < m; j++) {
            dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j]
        }
    }
    return dp[m - 1]
}

console.log("minPathSumComp: " + minPathSumComp(grid))

// 0-1 背包问题, 给定n个物品, 第i个物品的重量为wgt[i-1], 价值为val[i-1], 和一个容量为cap的背包, 每个物品
// 只能选择一次, 问在不超过背包容量下能放入物品的最大价值

// 状态转移方程
// 思考每一轮的决策, 对于每个物品来说, 不放入背包, 背包容量不变, 放入背包, 背包容量减小, 当前物品编号i和剩余背包容量c, 记为[i,c]
// 找出最优子结构
// 不放入物品i, 背包容量不变 状态变化为[i-1, c]  放入物品i 背包容量减小wgt[i-1], 价值增加val[i-1], 状态变化为 [i-1, c-wgt[i-1]]
// dp[n, cap] = max(dp[i-1, c], dp[i-1, cap-wgt[i-1]] + val[i-1])
// 确定边界条件和状态转移顺序
/**
 * @author hyun
 * @param wgt
 * @param val
 * @param i 物品编号
 * @param cap
 * @returns {number}
 */
function knapsackDFS(wgt, val, i, cap) {
    // 若已选完所有物品或背包没有容量
    if (i == 0 || cap == 0) {
        return 0
    }
    // 如果超过背包重量, 则不能放入背包
    if (wgt[i - 1] > cap) {
        return knapsackDFS(wgt, val, i - 1, cap)
    }
    // 计算放入物品与不放入物品i的最大价值
    const no = knapsackDFS(wgt, val, i - 1, cap)
    const yes = knapsackDFS(wgt, val, i - 1, cap - wgt[i - 1]) + val[i - 1]
    return Math.max(no, yes)
}

let wgt = [10, 20, 30, 40, 50]
let val = [50, 120, 150, 210, 240]
// console.log("knapsackDFS: " + knapsackDFS(wgt, val, wgt.length, 50))
console.log("knapsackDFS: " + knapsackDFS([10, 20, 20], [60, 110, 120], 3, 30))

// 记忆化搜索
function knapsackDFMem(wgt, val, mem, i, c) {
    if (i == 0 || c == 0) return 0
    if (mem[i][c] !== -1) return mem[i][c]
    if (wgt[i - 1] > c) return knapsackDFMem(wgt, val, mem, i - 1, c)
    const no = knapsackDFMem(wgt, val, mem, i - 1, c)
    const yes = knapsackDFMem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1]
    mem[i][c] = Math.max(no, yes)
    return mem[i][c]
}

const cap = 50
const __mem = Array.from({length: wgt.length + 1}, () => Array(cap + 1).fill(-1))
console.log("knapsackDFMem: " + knapsackDFMem(wgt, val, __mem, wgt.length, 50))

function knapsackDP(wgt, val, cap) {
    const n = wgt.length
    const dp = Array(n + 1).fill(0).map(() => Array(cap + 1).fill(0))
    for (let i = 1; i <= n; i++) {
        for (let c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                dp[i][c] = dp[i - 1][c]
            } else {
                dp[i][c] = Math.max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1])
            }
        }
    }
    return dp[n][cap]
}

console.log("knapsackDP: " + knapsackDP(wgt, val, 50))

/**
 * 状态压缩后的动态规划
 * @author hyun
 * @param wgt
 * @param val
 * @param cap
 * @returns {any}
 */
function knapsackDPComp(wgt, val, cap) {
    const n = wgt.length
    const dp = Array(cap + 1).fill(0)
    // 状态转移
    for (let i = 1; i <= n; i++) {
        for (let c = cap; c >= 1; c--) {
            if (wgt[i - 1] <= c) {
                // 不选和选物品i这两种方案的较大值
                dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
            }
        }
    }
    return dp[cap]
}

console.log("knapsackDPComp:" + knapsackDPComp(wgt, val, 50))

// 完全背包问题
// 给定n个物品, 第i个物品的重量为wgt[i-1], 价值为val[i-1], 和一个容量为cap的背包, 每个物品可以重复选取, 问在不超过背包容量下能放入物品的最大价值
// 不放入物品i 转移至 [i-1,c]
// 放入物品i 转移至[i, c-wgt[i-1]]
const newWgt = [10, 20, 30, 40, 50]
const newVal = [50, 120, 150, 210, 240]

/**
 * @author hyun
 * @param wgt
 * @param val
 * @param cap
 * @returns {number}
 */
function unboundedKnapsackDP(wgt, val, cap) {
    const n = wgt.length
    const dp = Array.from({length: n + 1}, () => Array.from({length: cap + 1}, () => 0))
    // 状态转移
    for (let i = 1; i <= n; i++) {
        for (let c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                dp[i][c] = dp[i - 1][c]
            } else {
                // 可以重复选取
                dp[i][c] = Math.max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1])
            }
        }
    }
    return dp[n][cap]
}

console.log("unboundedKnapsackDP: " + unboundedKnapsackDP(wgt, val, 50))

/**
 * 压缩后的完全背包问题, 由于当前状态是从左边和上边的状态转移而来, 因此空间优化后应该对dp表中的每一行采取正序遍历
 * @param wgt
 * @param val
 * @param cap
 * @returns {number}
 */
function unboundedKnapsackDPComp(wgt, val, cap) {
    const n = wgt.length
    const dp = Array.from({length: cap + 1}, () => 0)
    for (let i = 1; i <= n; i++) {
        for (let c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                dp[c] = dp[c]
            } else {
                dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
            }
        }
    }
    return dp[cap]
}

console.log("unboundedKnapsackDPComp: " + unboundedKnapsackDPComp(wgt, val, 50))

// 零钱兑换问题, 给定n种硬币, 第i种硬币的面值为coins[i-1],目标金额为amt, 每种硬币可以重复选取,
// 问能够凑出目标金额的最少硬币个数, 如果无法凑出目标金额返回-1
// 面值 coins[1,2,5], 目标金额 11

function minChangeDP(coins, amt) {
    const n = coins.length
    const MAX = amt + 1
    const dp = Array.from({length: n + 1}, () => Array.from({length: amt + 1}, () => 0))
    for (let a = 1; a <= amt; a++) {
        dp[0][0] = MAX
    }
    // 状态转移
    for (let i = 1; i <= n; i++) {
        for (let a = 1; a <= amt; a++) {
        }
    }
}